#pragma once

#include "IGraph.h"
#include <stack>
#include <map>

template <class Graph>
void DeepFirstSearch(const Graph &graph, std::vector <int> &in_time, std::vector <int> &out_time, bool is_sorting_on = 0)
{
    std::stack <int> unused_vertices;
    std::vector <short> is_used(graph.number_of_vertices(), 0);
    for (size_t start_vertix = 0, dfs_timer = 0; start_vertix < graph.size(); start_vertix++)
    {
        if (!is_used[start_vertix])
        {
            unused_vertices.push(0);
            while (!unused_vertices.empty())
            {
                size_t enter_vertix = unused_vertices.top();
                if (is_used[enter_vertix] == 1)
                {
                    is_used[enter_vertix] = 2;
                    out_time[enter_vertix] = dfs_timer++;
                    unused_vertices.pop();
                }
                else
                {
                    in_time[enter_vertix] = dfs_timer++;
                    is_used[enter_vertix] = 1;
                    graph.foreach_neighbour(enter_vertix, [&unused_vertices, &is_used](int node)
                                                          {
                                                              if (!is_used[node])
                                                              {
                                                                  unused_vertices.push(node);
                                                              }
                                                              if (is_used[node] == 1)
                                                              {
                                                                  throw std::runtime_error("DeepFirstSearch: topological sorting cannot be done on cyclic graph");
                                                              }
                                                          });
                }
            }
        }
    }
}

template <class Graph>
std::vector <int> TopologicalSorting(const Graph &graph)
{
    std::vector <int> in_time(graph.number_of_vertices(), 0), out_time(graph.number_of_vertices(), 0);
    std::vector <int> result;
    DeepFirstSearch(graph, in_time, out_time, 1);

    std::vector < std::pair<int, int> > out_time_with_vertices;
    for (size_t i = 0; i < out_time.size(); i++)
    {
        out_time_with_vertices.push_back(std::make_pair(out_time[i], i));
    }
    std::sort(out_time_with_vertices.begin(), out_time_with_vertices.end());
    for (auto it = out_time_with_vertices.rbegin(); it != out_time_with_vertices.rend(); it++)
        result.push_back(it -> second);
    return result;
}
